#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <corecrt.h>
#define MAX 100000
void swap(void* e1,void*e2,size_t width)
{
    char *s1 = (char*)e1,*s2 = (char*)e2;
    for(size_t i=0;i<width;i++)
    {
        char t = s1[i];
        s1[i] = s2[i];
        s2[i] = t;
    }
    return ;
}


void insert_sort(int* a,size_t len)
{
    for(size_t i=1;i<len;i++)
    {
        for(size_t k = i;k-1>0;k--)
        {
            if(a[k]>a[k-1])
            {
                swap(&a[k],&a[k-1],sizeof(a[k]));
            }
            else
            {
                break;
            }
        }
    }
    return ;
}


void shell_sort(int* a,size_t len)
{
    int gap = len;
    while(gap>1){
        gap = gap/4+1;
        for(int i=gap;i<len;i++)
        {
            for(int k=i;k-gap>=0;k-=gap)
            {
                if(a[k]>a[k-gap])
                {
                    swap(&a[k],&a[k-gap],sizeof(a[k]));
                }
                else
                {
                    break;
                }
            }
        }
    }
}


void bublle_sort(int* a,int n)
{
    for(size_t i=0;i<n;i++)
    {
        for(size_t k = i;k<n-i-1;k++)
        {
            if(a[k]<a[k-1])
            {
                swap(&a[k],&a[k-1],sizeof(a[k]));
            }
        }
    }
}






void test1(){
    srand(time(NULL));
    int c = MAX;
    int arr[c];
    for(int i=0;i<c;i++)
    {
        arr[i] = rand();
    }
    int time_begin1 = clock();
    shell_sort(arr,sizeof(arr)/sizeof(*arr));
    int time_end1 = clock();
    for(int i=0;i<c;i++)
    {
        arr[i] = rand()%10000;
    }
    int time_begin2 = clock();
    insert_sort(arr,sizeof(arr)/sizeof(*arr));
    int time_end2 = clock();
    printf("shell sort:  %d\nintsert_sort:  %d\n",time_end1-time_begin1,time_end2-time_begin2);
    time_begin1 = clock();
    shell_sort(arr,sizeof(arr)/sizeof(*arr));
    time_end1 = clock();
    for(int i=0;i<c;i++)
    {
        arr[i] = rand();
    }
    time_begin2 = clock();
    bublle_sort(arr,sizeof(arr)/sizeof(*arr));
    time_end2 = clock();
    printf("BuBlle sort:  %d\n",time_end2-time_begin2);
}


void Select_sort(int* a,int n)
{
    int fir = 0;
    int max_sub = 0;
    int min_sub = 0;
    int end = n-1;
    while(fir<end)
    {
        max_sub = fir;
        for(int i = fir;i<end;i++)
        {
            if(a[i]>a[max_sub])
            {
                max_sub = i;
            }
            if(a[i]<a[min_sub])
            {
                min_sub = i;
            }
        }
        swap(&a[fir],&a[max_sub],sizeof(a[fir]));
        swap(&a[end],&a[max_sub],sizeof(a[fir]));
        fir++;
        end--;
    }
}

void test2()
{
    srand(time(NULL));
    int c = MAX;
    int arr[c];
    for(int i=0;i<c;i++)
    {
        arr[i] = rand();
    }
    int time_begin1 = clock();
    Select_sort(arr,sizeof(arr)/sizeof(*arr));
    int time_end1 = clock();
    printf("Selectsort::  %d \n",time_end1-time_begin1);
}


int GetMid_Index(int *a,int left,int right)
{
    int mid = 0;
    mid = left+ rand()%(right-left);//三数，随机取中，这里应对leetcode的一些专门设计的数据
    if(a[mid]>a[left])
    {
        if(a[mid]<a[right])
        {
            return mid;
        }
        else if(a[left]>a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else //mid<left
    {
        if(a[mid]>a[right])
        {
            return mid;
        }
        else if(a[right]<a[left])
        {
            return right;
        }
        else
        {
            return left;
        }
    }
}
int part_sort(int *a,int n)
{
    if(n<=1)
    {
        return 0;
    }
    int midi = GetMid_Index(a,0,n-1);
    swap(&a[0],&a[midi],sizeof(a[0]));
    int i =0;
    int temp = a[0];
    int m = n -1;
    for(int j=0;j<m+1;)//前后指针交换
    {
        if(a[j]==temp)
        {
            j++;
        }
        else if(a[j]<temp)
        {
            swap(&a[i++],&a[j],sizeof(a[j]));
            j++;
        }
        else
        {
            swap(&a[m--],&a[j],sizeof(a[j]));
        }
    }
    a[i] = temp;
    return i;
}

void quick_sort(int *a,int n)//cursion
{
    
    int i = part_sort(a,n);
    if(i>0)
    {
        quick_sort(&a[0],i);
    }
    if(n-i-1>0)
    {
        quick_sort(&a[i+1],n-i-1);
    }
    return ;
}


//迭代的思路，根据快排核心思想：分成中间数，左右两边的数。
//只要左右两边的数字排序好了，那么，快排也就排序完毕
//那么快排的时候，就是一种树
//那么如何迭代呢
//树里面唯一迭代属性的就是层序遍历
//快排迭代属性也差不多，假想我们给快排已经切割好了数组，左数组，中值，右边数组
//如此直到最后一层只剩一个中值，开始向上递归
//也就是说,最后展开的那个左数组，中值，右数组，（此时就剩下中值）
//需要我们最先处理
//那么这其实和栈的性质就不约而同一样了：先进后出
//也就是说，不断分割，将左数组和右数组存入进栈，再不断分割，当某一部分数组有序后，则出栈，直至每一个数据排序完毕出栈即可，直至栈空则排序完毕

//那么基本思路有了，关键就是压栈出栈
//因为我们其实要传两个属性，一个数组（或者说整形指针，一个数组的大小，考虑使用结构体时ok的
//也可以换一种办法，数组一直都是a，我们可以压栈压左右两个下标，对a解引用取地址即可表示数组

void quick_sort_iteration(int *a ,int n)//iteration
{   
    if(a==NULL)
    {
        perror("a == NULL!\n");
    }
    int* stack = (int*)realloc(NULL,sizeof(int)*10);
    if(stack==NULL)
    {
        perror("malloc fail");
    }
    int Stack_size = 10;
    int left = 0;
    int right =  n-1;
    int c = 0;
    stack[c++] =  left;
    stack[c++] = right;
    while (c>0)
    {
        if(c+4>Stack_size)
        {
            stack = realloc(stack,(Stack_size*=2) * sizeof(int));
        }
        right = stack[--c];
        left = stack[--c];
        if(right-left+1<10)
        {
            Select_sort(&a[left],right-left);continue;
        }
        int i = part_sort(&a[left],right-left+1)+left;
        if(i-left>1)
        {
            stack[c++] = left;
            stack[c++] = i-1;
        }
        if(right-i>1)
        {
            stack[c++] = i+1;
            stack[c++] = right;
        }
    }
    free(stack);
}


int part_sort_returnArrays(int * a,int n,int* returnSize)//如果说，存在全都相等的数字，那么这里不就是单趟遍历，最后导致quiksort是n^2的时间复杂度
//因此这里提供一种修改方案，相等的全部移往中间，但是值得注意，由于返回相当于是一个数组了，那么就不仅仅要i下标，还要整个长度
{

    if(n<=1)
    {
        return 0;
    }
    int midi = GetMid_Index(a,0,n-1);
    swap(&a[0],&a[midi],sizeof(a[0]));
    int i =0;
    int temp = a[0];
    int count = 0;//计算与temp值相等的数值总个数
    int m = n -1;
    for(int j=0;j<m+1;)//前后指针下标版本
    {
        if(a[j]==temp)
        {
            count++;
            j++;
        }
        else if(a[j]<temp)
        {
            swap(&a[i++],&a[j],sizeof(a[j]));
            j++;
        }
        else
        {
            swap(&a[m--],&a[j],sizeof(a[j]));
        }
    }
    for(int k = 0;k<count;k++)//注意，由于这里每次都多走了一组，实际效率有所下降,
    {
        a[i+k] = temp;
    }
    *returnSize = count;
    return i;
}
void quick_sort_iteration_ver2(int *a ,int n)//iteration
//解决有多个相同数据的问题
{   
    if(a==NULL)
    {
        perror("a == NULL!\n");
    }
    int* stack = (int*)realloc(NULL,sizeof(int)*10);
    if(stack==NULL)
    {
        perror("malloc fail");
    }
    int Stack_size = 10;
    int left = 0;
    int right =  n-1;
    int c = 0;
    stack[c++] =  left;
    stack[c++] = right;
    while (c>0)
    {
        if(c+4>Stack_size)
        {
            stack = realloc(stack,(Stack_size*=2) * sizeof(int));
        }
        right = stack[--c];
        left = stack[--c];
        int MidArayySize = 0;
        int i = part_sort_returnArrays(&a[left],right-left+1,&MidArayySize)+left;
        if(i-left>1)
        {
            stack[c++] = left;
            stack[c++] = i-1;
        }
        if(right-i>1)
        {
            stack[c++] = i+MidArayySize;
            stack[c++] = right;
        }
    }
    free(stack);
}





void test3()
{
    srand(time(NULL));
    int c = MAX;
    int arr[c];
    for(int i=0;i<c;i++)
    {
        arr[i] = rand();
        // arr[i] = MAX-i;
    }
    int time_begin1 = clock();
    quick_sort_iteration(arr,sizeof(arr)/sizeof(*arr));
    int time_end1 = clock();
    printf("quick_sort_interation:  %d \n",time_end1-time_begin1);
    for(int i=0;i<c;i++)
    {
        // arr[i] = 2;
        arr[i] = rand();
        // arr[i] = MAX-i;
    }
    time_begin1 = clock();
    quick_sort_iteration_ver2(arr,sizeof(arr)/sizeof(*arr));
    time_end1 = clock();
    printf("quick_sort_interation_ver2:  %d \n",time_end1-time_begin1);
}

int* arrs_sort(const int *arr,const int* brr,const int sz1,const int sz2)//这里会申请动态太内存，调用函数请记得释放 ,返回数组的大小一定就是sz1+sz2 
{
	int* rearrs = (int*)malloc(sizeof(int)*(sz1+sz2));
	int c = 0; 
	int a = 0,b = 0;
	int sign = a<sz1 ;
    sign += b<sz2;
	while(sign)
	{
		switch(sign)
	{
		case 2:
			{
				if(arr[a]>brr[b])
				{
					rearrs[c++] = brr[b++];
				}
				else
				{
					rearrs[c++] = arr[a++];
				}
				break;
				
			}
		case 1:{
			if(a<sz1)
			{
				rearrs[c++] = arr[a++];
			}
			else if (b<sz2)
			{
				rearrs[c++] = brr[b++];
			}
			break;
		}
		default :break;
	}
    sign = a<sz1;
    sign += b<sz2;
	}
	return rearrs; 
} 
//归并排序
//迭代版本

// int* arrs_sort_NonMalloc(const int *arr,const int* brr,const int arr_sz,const int brr_sz)//必须保证第一个数组大小时，sz1是arr传过来要排序
// {
// 	int a = 0,b = 0;
//     while(b<brr_sz)
//     {

//     }
// 	return arr; 
// } 
int merge_sort(int arr[],int sz)
{
    int a = 2;
    for(;a/2<sz;a*=2)
    {
        for(int i=0;i<sz;i+=a)
        {
            if(i+a<=sz)
            {
                int *t = arrs_sort(&arr[i],&arr[i+a/2],a/2,a/2);
                memmove(&arr[i],t,a*sizeof(int));
                free(t);
            }
            else if(i+a/2<sz)
            {
                int *t = arrs_sort(&arr[i],&arr[i+a/2],a/2,sz-a/2-i);
                memmove(&arr[i],t,(sz-i)*sizeof(int));
                free(t);
            }
        }
    }
    return 0;
}
//归并排序的迭代版本

void test4()
{
    srand(time(NULL));
    int c = MAX;
    int arr[c];
    for(int i=0;i<c;i++)
    {
        arr[i] = rand();
    }
    int time_begin1 = clock();
    merge_sort(arr,sizeof(arr)/sizeof(*arr));
    int time_end1 = clock();
    printf("mergesort:: %d \n",time_end1-time_begin1);
}



//堆排序

void adjust_down(int* a,int pos_now,int is_little,int size)//向下调整
{
    int i = pos_now;
    if(is_little>0)
    {
        int j = i*2+1;
        while(j<size)
        {
            if(j+1<size && a[j+1]>a[j])
            {
                j++;
            }
            if(a[j]>a[i])
            {
                swap(&a[i],&a[j],sizeof(int));
            }
            else
            {
                break;
            }
            i = j;
            j = i*2+1;
        }
    }
    else
    {
        int j = i*2+1;
        while(j<size)
        {
            if(j+1<size && a[j+1]<a[j])
            {
                j++;
            }
            if(a[j]<a[i])
            {
                swap(&a[i],&a[j],sizeof(int));
            }
            else
            {
                break;
            }
            i=j;
            j = i*2+1;
        }
    }
}
void heapsort(int *arr,int len)
{
    // for(int i=0;i<len;i++)
    // {
    //     adjust_up(arr,i,-1,i+1);
    // }
    // for(int j = 0;j<len-1;j)
    // {
    //     swap(arr,arr+len-1-j++,sizeof(int));
    //     adjust_down(arr,0,-1,len-j);
    // }//向上建堆
    for(int i =(len-2)/2;i>=0;i--)
    {
        adjust_down(&arr[i],0,1,len-i);
    }
    for(int i = 0;i<len-1;i)
    {
        swap(arr,arr+len-1-i++,sizeof(int));
        adjust_down(arr,0,1,len-i);
    }
    int b = 0;
    return;
}


void test5()
{
    srand(time(NULL));
    int c = MAX;
    int arr[c];
    for(int i=0;i<c;i++)
    {
        arr[i] = rand();
    }
    int time_begin1 = clock();
    heapsort(arr,sizeof(arr)/sizeof(*arr));
    int time_end1 = clock();
    printf("heapsort:: %d \n",time_end1-time_begin1);
}


void count_sort(int *a,int n)
{
    int min = a[0];
    int max = a[0];
    for(int i = 1;i<n;i++)
    {
        if(a[i]>max)
        {
            max = a[i];
        }
        if(a[i]<min)
        {
            min = a[i];
        }
    }
    int * arr= (int*)malloc(sizeof(int)*(max-min+1));
    memset(arr,0,sizeof(int)*(max-min+1));
    for(int i =0;i<n;i++)
    {
        arr[a[i]-min]++;
    }
    int c = 0;
    for(int i=0;i<max-min+1;)
    {
        if(arr[i]>0)
        {
            a[c++] = i+min;
            arr[i]--;
        }
        else
        {
            i++;
        }
    }
    free(arr);
}

void test6()
{
    srand(time(NULL));
    int c = MAX;
    int arr[c];
    for(int i=0;i<c;i++)
    {
        arr[i] = rand();
    }
    int time_begin1 = clock();
    count_sort(arr,sizeof(arr)/sizeof(*arr));
    int time_end1 = clock();
    printf("count_sort:: %d \n",time_end1-time_begin1);
}


int main()
{
    // test1();
    // test2();
    test3();
    test4();
    test5();
    test6();
    system("pause");
    return 0;
}